package week_06;

public class MazeBollHashPathStop {
    // 四个方向 前进 北 东 南 西
    int[] dx = new int[]{0, 1, 0, -1};
    int[] dy = new int[]{1, 0, -1, 0};
    boolean[][] isVisit;
    int m;
    int n;
    int[][] maze;
    int[] destination;

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        m = maze.length;
        n = maze[0].length;
        isVisit = new boolean[m][n];
        this.destination = destination;
        this.maze = maze;
        return find(maze, start[0], start[1]);
    }

    public boolean find(int[][] maze, int x, int y) {

        if (x == destination[0] && y == destination[1]) return true;
        // 四个方向尝试

        System.out.println("x:" + x + ":y:" + y + ":isVisit:" + isVisit[x][y] + ":maze:" + maze[x][y]);
        boolean res = false;
        isVisit[x][y] = true;
        for (int k = 0; k < 4; k++) {

            int nx = x;
            int ny = y;
            while (!isOver(nx, ny) && maze[nx][ny] == 0) {
                nx += dx[k];
                ny += dy[k];
            }
            nx -= dx[k];
            ny -= dy[k];

            if (maze[nx][ny] == 0 && isVisit[nx][ny] == false) res = res || find(maze, nx, ny);
        }
        return res;
    }

    public boolean isOver(int x, int y) {
        return x < 0 || y < 0 || x >= m || y >= n;
    }

    public static void main(String[] args) {

        int[][] maze = new int[][]{{0, 0, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0}};
        int[] start = new int[]{4, 3};
        int[] destination = new int[]{0, 1};
        MazeBollHashPathStop test = new MazeBollHashPathStop();
        System.out.println(test.hasPath(maze, start, destination));
    }
}
